// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
	name = debugName;
	value = initialValue;
	queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
	delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
	Semaphore::P()
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
	DEBUG('S', "Semaphore %s P().\n", name);
	while (value == 0) { 			// semaphore not available
		queue->Append((void *)currentThread);	// so go to sleep
		currentThread->Sleep();
	} 
	value--; 					// semaphore available, 
						// consume its value
	DEBUG('S', "Semaphore %s P() Exit.\n", name);
	(void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
	Semaphore::V()
{
	Thread *thread;
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	DEBUG('S', "Semaphore %s V().\n", name);
	thread = (Thread *)queue->Remove();
	if (thread != NULL)	   // make thread ready, consuming the V immediately
		scheduler->ReadyToRun(thread);
	value++;
	DEBUG('S', "Semaphore %s V() Exit.\n", name);
	(void) interrupt->SetLevel(oldLevel);
}

//----------------------------------------------------------------------
// Lock::Lock(char* debugName)
//      initialize a Lock.
//      debugName: name for debug
//----------------------------------------------------------------------
Lock::Lock(char* debugName) 
{
	name = debugName;
	queue = new List;
	holder = NULL;
}

//----------------------------------------------------------------------
// Lock::~Lock()
//      Dealloc a Lock, assume no thread is holding the lock
//----------------------------------------------------------------------
Lock::~Lock() 
{
	delete queue;
}

//----------------------------------------------------------------------
// Lock::Acquire()
//      if the lock is free, then current thread acquire the lock
//      otherwise the thread waiting in the queue for the lock to
//      be released.
//      first check if the thread is acquire the lock twice, and ignore
//      the duplicate request.
//----------------------------------------------------------------------
void Lock::Acquire() 
{
	if(isHeldByCurrentThread()) {
	// a thread cannot hold the lock twice.
	// ignore the request
		return;
	}

	IntStatus oldLevel = interrupt->SetLevel(IntOff);
// make the operation atomic.

	if (holder == NULL) {
	// no thread is holding the lock
		holder = currentThread;
	}
	else {
	// some other thread is holing the lock, put the thread in the
	// waiting list.
		queue->Append((void *)currentThread);
		currentThread->Sleep();
	}
	(void) interrupt->SetLevel(oldLevel);
// restore the old interrupt level.
}

//----------------------------------------------------------------------
// Lock::Release()
//      set the lock to be free, and if there's other threads waiting 
//      for acquiring the lock, then the first thread in the queue 
//      acquires the thread
//      first check if current thread is also the lock holder, otherwise
//      ignore the request.
//----------------------------------------------------------------------
void Lock::Release() 
{
	if(!isHeldByCurrentThread()) {
	// only the lock holder can release the lock.
	// ignore the request
		return;
	}

	IntStatus oldLevel = interrupt->SetLevel(IntOff);
// make the operation atomic.

	Thread *thread = (Thread *)queue->Remove();
	if (thread != NULL) {
		scheduler->ReadyToRun(thread);
	}
	holder = thread;
// make the next thread acquire the lock.

	(void) interrupt->SetLevel(oldLevel);
// restore the old interrupt level.
}

//----------------------------------------------------------------------
// Lock::isHeldByCurrentThread
//      return true if the current thread is holding the lock
//      useful in Release()
//----------------------------------------------------------------------

bool Lock::isHeldByCurrentThread() {
	return (currentThread==holder);
}

//----------------------------------------------------------------------
//Condition::Condition
//          initialize a Condition
//          waiting list:a threads waiting list, put thread into it 
//                       when Wait()
//----------------------------------------------------------------------
Condition::Condition(char* debugName)
{
	name = debugName;
	waitinglist = new List;
}
//----------------------------------------------------------------------
//Conditon::~Condition
//          delete a Condition
//----------------------------------------------------------------------
Condition::~Condition() 
{
	delete waitinglist;
}
//----------------------------------------------------------------------
//Condition::Wait
//           Check whether is held by current thread   
//           if true, then first forbid interrupt because realse and
//           sleep is atomic
//           realse the lock held by current thread then put the 
//           thread into waitinglist and end atomic status
//           at last a new thread get the lock
//----------------------------------------------------------------------
void Condition::Wait(Lock* conditionLock) 
{
//only current thread who owns lock that can wait
	if(!conditionLock->isHeldByCurrentThread())
	{
		return;
	}

//release is atomic
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	conditionLock->Release();
	Condition::ThreadInfo *info = 
		new Condition::ThreadInfo(currentThread, conditionLock);
	waitinglist->Append((void*)info); //or conditionLock.holder
	currentThread->Sleep();
//after event,atomic status is remove
	(void)interrupt->SetLevel(oldLevel);

//a new thread gain lock
	conditionLock->Acquire();
}

//----------------------------------------------------------------------
//Condition::Signal()
//           inform thread in the top of waiting list to wake up
//           then the thread change into ready status
//           ReadyToRun must be atomic
//----------------------------------------------------------------------
int Condition::Signal(Lock* conditionLock) 
{
//while conditionLock isn't held by current thread 
//then ignore signal request
	if(!conditionLock->isHeldByCurrentThread())
	{
		return 0;
	}

	int rv = 0;

//get a thread from waiting list
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	List* tempList = new List;
	Condition::ThreadInfo* info = 
		(Condition::ThreadInfo*)waitinglist->Remove();

	while (info != NULL && info->lock != conditionLock) {
		tempList->Prepend((void*)info);
		info = (Condition::ThreadInfo*)waitinglist->Remove();
	}
	Condition::ThreadInfo* tempInfo = 
		(Condition::ThreadInfo*)tempList->Remove();
	while (tempInfo != NULL) {
		waitinglist->Prepend(tempInfo);
		tempInfo = (Condition::ThreadInfo*)tempList->Remove();
	}
	delete tempList;
	if (info != NULL)
	{
	//wake up thread, make it ready
		rv = 1;
		scheduler->ReadyToRun(info->thread); 
		delete info;
	}
	(void)interrupt->SetLevel(oldLevel);
	return rv;
}

//----------------------------------------------------------------------
//Condition::Broadcast
//           inform all threads in waiting list to wake up
//           each of them change into ready status
//----------------------------------------------------------------------
int Condition::Broadcast(Lock* conditionLock) 
{
//check whether lock is held by current thread
	if(!conditionLock->isHeldByCurrentThread())
	{
		return 0;
	}
	
	int rv = 0;

	List *tempList = new List;
	Condition::ThreadInfo* info = (Condition::ThreadInfo*)waitinglist->Remove();
	while(info != NULL)
	{
		IntStatus oldLevel = interrupt->SetLevel(IntOff);
		if (info->lock == conditionLock) {
			rv++;
			scheduler->ReadyToRun(info->thread);
			delete info;
		}
		else 
			tempList->Prepend((void*)info);
		(void)interrupt->SetLevel(oldLevel);
		info = (Condition::ThreadInfo*)waitinglist->Remove();
	}
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	info = (Condition::ThreadInfo*)tempList->Remove();
	while (info != NULL) {
		waitinglist->Prepend((void*)info);
		info = (Condition::ThreadInfo*)tempList->Remove();
	}
	delete tempList;
	(void)interrupt->SetLevel(oldLevel);
	return rv;
}
